\documentclass[a4paper,11pt]{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[danish]{babel}
\usepackage{listings}
\usepackage{graphicx}
\usepackage{fancyhdr}
\pagestyle{fancy}
\fancyhead[LE,LO]{\textbf{Compiler Construction}}
\fancyhead[RE,RO]{\textit{Philip Thyssen \& Michael Franz (Group 4)}}

\lstset{basicstyle=\footnotesize, tabsize=3, numbers=left, stepnumber=1}
\lstdefinelanguage{none}{morekeywords={thisisnotakeyword}}
\lstdefinelanguage{rajah}{morekeywords={func, end, int, bool, array, of,
record, type, var, return, write, allocate, if, then, while, do, length,
else, true, false, null, break, continue},
morecomment=[l]{\#}, morecomment=[n]{(*}{*)} }
\title{Compiler Construction, part 3}
\author{Philip Thyssen \& Michael Franz}
\date{Tuesday, Marts 25, 2011}

\begin {document} 
\maketitle
\newpage
\renewcommand{\contentsname}{Table of contents}
\tableofcontents
\newpage
\section{Introduction}
The third part of the compiler construction contains two tasks. First, the abstract syntax tree will go through a weed phase where it is verified if
 a function has a return statement. Second, the AST is used to traverse through the tree inorder to perform typechecking. Typechecking requires three passes
\begin{verbatim}
1. Collecting all the identifiers in the declarations and
   putting them in the proper symboltable(scope)
2. Calculating types for all expressions and subexpressions
3. Verifying correct use of types. 
\end{verbatim} 
\section{Weeder}
In general, a weeders main purpose is to do very rough optimizing of an AST. This could be deleting code which never would be executed or verifying that each function has a return
statement etc. This weeder only does the bare minimum, it verifies that each function has a return statement. Another requirement, which was  verifying that each function has
starts and ends with the same name was implemented in the parser. \\ The weeder works by traversing down through the tree only entering those branches which will lead to a return statement.
There are only two options, either a bare return statement or return statements in an if-else construction. In a if-else statement one part will be entered which is why a return 
is required in both outside any conditional branch.    
\subsection{implementation}
The implementation of this weeder is straight forward, the traversal happens recursively. Its only functions who are traversed through, the main idea of the implementation is to 
return 1, in case a return statement was found for a function. The most difficult part of this part is to make sure its only if-else that are evaluated: 
\begin{lstlisting}
case ifK:
    if (!stat->val.ifE.opt_else == 0) {
      int weeded_if = weed_if_statement(stat->val.ifE.statement);
      int weeded_else = weed_else_statement(stat->val.ifE.opt_else);
      if (weeded_if && weeded_else) {
      return 1;
      }
   }
 break;
\end{lstlisting}
An if statement is only evaluated if else is represented, then if both if and else returns one, it means a return statement is represented in both cases.   
\section{Scopes and Symboltable - Pass 1 and Pass 2}
The first pass of typechecking is dedicated to the collection of identifiers declared in declarations. Another important aspect of this pass is to create a scope for each the main body and
for each function declared. The convention followed with scopes is the one covered during the course DM516. The 'main' body's symboltable works as a root the the rest. This 
means that every type or variable declared in the main is visible to every function declared. Every function declared within another function, has the scope available that the
outer function owns. However, every identifier that is defined in the outer shell can be redefined within a function. It takes two passes to completly finish validating delcaration\\
Consider this small example:\\
\begin{verbatim}
 type a = b;
  var c: a; 
 type b= int;
\end{verbatim}
The problem is a nested type/variable declaration, meaning that the final existence of their type can first be validated in a second pass. The second pass has been combined with 
calculating expressions and subexpressions. Every identifier's type will be looked up in the symboltable, if it exist it means that it has be registered. 
Another problem that evolves is loops within types:
\begin{verbatim}
 type a= b;
 type b= c;
 type c= a;
\end{verbatim}
This very simple example shows a circle that should be detected and reported as an error. The main idea behind detecting circles is about:homethe following: \\
During the second pass, every type and variable declared by a type will be traversed, everytime a type is meet it will be added as a symbol in a temporary symboltable, if a
`solid` type is meet, the check is terminated, if at somepoint a symbol is put that already exist a circle is detected. Another thing which has to be taken into account is the
following situation.
\begin{verbatim}
 type c= a;
 type a= int;
 func(a:int)
    type a=b;
    type b=c;
  end func
\end{verbatim}
In this case, 'a' defined outside of the function is not the same as the one assigned within the function. The main point is, that whenever a type or variable is assigned 
with a type from another scope, this type can not cause any circles within the innner function. There could be a circle but they would be in the outer declaration.\\ The last thing
that is perfomed during this stage is a cleanup of every variable. Meaning that type acts like a macro, everywhere where a type declaration is used it is being replaced by
real type. The reason for why a 'cleaner' is implemented is because it eases the comparison between types at a later stage.  
\subsection{implementation - General structur}
The implementation of the first run is straight forward.The declarations in  main body and in any declaration within a function are being recursed. Every time an identifier is
meet a symbol is added to the corresponding scoop. Everytime a function is meet a new table is being scooped, furthermore everytime a record is meet a new symboltable is 
initialized, since those variable types delcared in here are not accesible for anyone outside the record: 
\begin{lstlisting}
void run1TYPE(TYPE *type, SymbolTable *symboltable){
  if(type->kind == recordK){
    type->val.recordE.table= initSymbolTable();
    run1VAR_DECL_LIST(type->val.recordE.var_decl_list,
			      type->val.recordE.table);
    }else if(type->kind == arrayK){
     run1TYPE(type->val.type, symboltable);
    }
}
\end{lstlisting}
 Every time one of the three identifier are meet a symbol is put in the symboltable:
\begin{lstlisting}
 case typeidK:
        symbol = putSymbolType(symboltable,
	      declaration->val.DECL_TYPE.id,declaration->val.DECL_TYPE.type);


 case funcK:
        function = declaration->val.function;
        head = function->head;
        body = function->body;
        symbol = putSymbolFunction(symboltable, head->id,function);

void run1VAR_TYPE(VAR_TYPE *var_type, SymbolTable *symboltable){
        SYMBOL *symbol;
        symbol = putSymbolVariable(symboltable, var_type->id,var_type);

\end{lstlisting}
\subsection{Implementation - 2 pass}
During the second pass the declaration are run through again. If an identifier is assigned by an type declaration, the existens of the type is checked by a call to getSymbol:
\begin{lstlisting}
case type_idK:
       symbol=getSymbol(symboltable, type->val.id);
       if(symbol==NULL) {
           run2Error++;
           fprintf(stderr,"Error:%d: '%s' undeclared\n", type->lineno, type->val.id);
         }
        break;
\end{lstlisting}
The existens of the type is checked within the scope, however if no symbol is returned this type has not be declared within this environment.
\subsection{Implementation - Check Loop}
Inorder to avoid loopes,a newly initialized symboltable is used for each type that is check recursively. Everytime the recursion went one level deeper the type is added to the symboltable.
If a type failed to be inserted it means it already exist in the table and therefore a loop is reported:
\begin{lstlisting}
 void run2LOOPCHECK(DECLARATION *declaration, SymbolTable *symboltable){
        SymbolTable *temp;
        temp = initSymbolTable();
        putSymbolType(temp, declaration->val.DECL_TYPE.id,NULL);
        run2LOOPTYPE(declaration->val.DECL_TYPE.type, symboltable, temp);

void run2LOOPTYPE(TYPE *type, SymbolTable *symboltable,SymbolTable *temp)
.
.
 if(type->kind == type_idK){
       int index = Hash(type->val.id);
       SYMBOL *symbol;
       symbol = symboltable->table[index];
       if(symbol!=NULL){
             while(strcmp(symbol->name, type->val.id)!=0 && 
					 symbol->next!=NULL){
                   symbol = symbol->next;
                }
              if(strcmp(symbol->name, type->val.id)==0){
                      /*
                      * Symbol found in SymbolTable we now need to check
                     * if it exists in the temporary SymbolTable
                    */

\end{lstlisting}about:home
 The last part shows how to make sure, that the type which is being performed a check on exist within the types defined by the most inner 'scope'. The reason getSymbol could not be used
is due to the fact the it doesnt return any information from what level the symbol was at.  
\subsection{Implementation - run2GETTYPE (clean type)}
The clean type implementation is straight forward. The base case is of course a type, this is what has to be removed:
\begin{lstlisting}
 TYPE *run2GETTYPE(TYPE *type, SymbolTable *symboltable){
   if(type->kind == type_idK){
       SYMBOL *symbol;
       symbol = getSymbol(symboltable, type->val.id);
       if(symbol!=NULL){
            return run2GETTYPE(symbol->val.type, symboltable);
           }
        }
\end{lstlisting}
This is done be returning the actual pointer to the type in the AST instead of a declaration of the type. 
\section{Calculation of expressions - Pass2}
In the second part of pass two, the statement lists are run through. The goal is to calculate every expression, this means that every expression variable and term should have a calculated type 
after this run. The approach is to recurse all the way down until the leafs of the tree, from there calculate the types of each expression. Expression which ends in either a 
boolean or an integer are easy to handle, however variables are more complicated. \\ 
Since variable is defined recursively, variable has to be recursed all the way down. For variable, 'id' is the base case, once 'id' is accessed it can be used to obtain the entire type
via the symboltable which will be return. There are two more cases, array and record. Both of them have the same approach: the type is found recursively which is assigned to 
this nodes type, what is returned is the same type without the most right part. In this way from one level to the next one the type is getting `shorter` and is assigned to each
node along the road until the last part. There is a special case in 'record', since the type of the variable which is accessed within record has to be returned.  
\subsection{implementation}
There are two bigger parts where the actual type is calculated: term, variable. Everything else is recursive calls to reach the bottom of the tree. 
Every expression consists of 2 children except the basecase which is term. Term is responsible for all the primitive types, such as int and bool etc. The only case which is a little
more complex is the one for a function call:
\begin{lstlisting}
 case term_idK:
   symbol = getSymbol(symboltable, term->val.term_idE.id);
   if(symbol!=NULL){
      if(symbol->kind == functionSK){
         head = symbol->val.function->head;
         term->type = head->type;
         act_list = term->val.term_idE.act_list;
           if(act_list!=0){
             run2EXP_LIST(act_list->exp_list, symboltable);
             }
 return term->type;
\end{lstlisting}
What actually is being done, is getting the return type of the function being called and assigned to the node making it easy accesible for the last run. \\
The next big part is the one described above. The variables are a litte more complex to calculate. There are the possibility for nested records and arrays which makes it more 
difficult. This part of the code contains some redundant code due to a sligthly change in approach. At the beginning this was coded without a 'clean-type', which means there were
certain scenarios that had to be taken care of. After implementing a 'clean-type' those scenarios are redundant however the code is not changed right now due to a time-constraint.
The code will be updated as soon as possible, however there will be no detailed discussion about the variable part for now. 
\section{Verification of types - Pass 3}
In the last part of the typechecker, the typechecking is perfomed. The idea is, that wherever there is a type to be checked the type is already calculated and available within the node.
The one function that is really important and is new in comparison to the other runs is the comparison between types. Types are verified as equal if everything is equivalent
except the names of the var_types within records as long as they have the same type and come in the same order. The Approach for verifying types are the following: recursion until statements and then validating evey statement accordingly to to its structure. These structures will recursively callexpressions, variable and term.
\subsection{Implementation}
There are several important parts to cover: statement, expression, term  and compare types. For each part only one case will be covered since there are many cases.
\subsection{Implementation - statement}
To illustrate how to verify the case if will be used. 
\begin{lstlisting}
case ifK:
expression = statement->val.ifE.expression;
run3EXPRESSION(expression, symboltable);
type = expression->type;
if(type->kind != boolK){
   run3Error++;
   fprintf(stderr,"Error:%d: expression for if-statement not bool\n", statement->lineno);
}
run3STATEMENT(statement->val.ifE.statement, symboltable, func_id);
opt_else = statement->val.ifE.opt_else;
if(opt_else!=0){
   run3STATEMENT(opt_else->statement, symboltable, func_id);
}
 break;
\end{lstlisting}
'If' consists of an expression which should be evaluated to a boolean, it only makes sense if it evaluates to either true or false. Expressions 
is called recursively since other expressions below with an operator might have unresolved types in comparison to the operator. Hereafter the statement list
 is evaluated recursivley to evaluated the rest of the statements. Furthermore, in case 'else' exists statement list is also evaluated recursively. Basically for every 
statement, there types are called accordingly to there structure. 
\subsection{Implementation - expression}
In expression there is always a comparison between the left and the right child except in the basecase which is term:
\begin{lstlisting}
case neqK:
 exp1 = expression->val.EXPneq.left;
 exp2 = expression->val.EXPneq.right;
 type1 = run3EXPRESSION(exp1, symboltable);
 type2 = run3EXPRESSION(exp2, symboltable);
 if(run3COMPARE_TYPES(type1,type2)==1){
   run3Error++;
   fprintf(stderr, "Error:%d: incompatible type for expression\n",
						expression->lineno);
  }
  return expression->type;
  break;
\end{lstlisting}
First, not-equal evaluates its expression where after it compares type. There are no restrictions, since not-equal should be able to compare booleans with each other but also integers.
\subsection{Implementation - term}
In term there are several cases, where only one case is a little complicated which was adressed shortly earlier, the function call:
\begin{lstlisting}
act_list = term->val.term_idE.act_list;
symbol = getSymbol(symboltable, term->val.term_idE.id);
if(symbol!=NULL){
 if(symbol->kind == functionSK){
  head = symbol->val.function->head;
  if(act_list!=0){
    if(head->par_decl_list!=0){
      par_decl_list = head->par_decl_list;
      if(run3COMPARE_FUNC(act_list->exp_list, 
	      par_decl_list->var_decl_list)==1){

\end{lstlisting}
The interesting thing here is that 'exp-list' contains all the calling arguments and the variable declaration list contains all the types for what is expected of the arguments. 
\subsection{Implementation - run2COMPARETYPES}
Looking at the implementation of comparing types, its fairly simple. The approach is to take to types as arguments and the first part of their types and then recurse over them.
\section{test}
\begin{verbatim*}
 returnStatement.raj
INPUT----------------------------------------------------
func a(): int
	func b():int
		return true;
	end b
	func c():int
		return 42;
	end c
	write 42;
end a
write(a());
OUTPUT---------------------------------------------------
Error:1: function 'a' missing return statement
Error:3: return type is not the same as function(b) type
***2 errors found***



recordTest.raj
INPUT----------------------------------------------------
type l = record of {t:int} ;
var b : l;
var i : int;
var c : array of l;
b.t = 42;
i = 1;
c[1].t = 42;
write c[i].t;

OUTPUT---------------------------------------------------
type l = record of {t:int};
var b:record of {t:int};
var i:int;
var c:array of record of {t:int};
b(*record*).t(*int*) = 42(*int*);
i(*int*) = 1(*int*);
c(*array*)(*record*)[1(*int*)](*record*).t(*int*) = 42(*int*);
write(c(*array*)(*record*)[i(*int*)](*record*).t(*int*));




recordTest2.raj
INPUT----------------------------------------------------
type b = record of {t:int};
var a : b;
func c(): int
	var d:b;
	d.t = 42;
	return d.t;
end c
write a.t;
OUTPUT---------------------------------------------------
type b = record of {t:int};
var a:record of {t:int};
func c(): int
   var d:record of {t:int};
   d(*record*).t(*int*) = 42(*int*);
   return d(*record*).t(*int*);
end c 
write(a(*record*).t(*int*));



recordTest3.raj
INPUT----------------------------------------------------
type p = record of {t:int};
var b : array of p;
var result : int;
b[1].t = 42;
result = b[1].t;
write result;
OUTPUT---------------------------------------------------
type p = record of {t:int};
var b:array of record of {t:int};
var result:int;
b(*array*)(*record*)[1(*int*)](*record*).t(*int*) = 42(*int*);
result(*int*) = b(*array*)(*record*)[1(*int*)](*record*).t(*int*);
write(result(*int*));



typeCycle.raj
INPUT----------------------------------------------------
type b = e;
type a = b;
func c():int
	type b = d;
	type d = e;
	return 42;
end c
type e = a;

write 42;
OUTPUT---------------------------------------------------
Error:1: type 'b' ends in a type-loop
Error:2: type 'a' ends in a type-loop
Error:8: type 'e' ends in a type-loop
***3 errors found***


functionRecordTest.raj
INPUT----------------------------------------------------
type z = int;
type q = record of {i:z};
type l = array of q;
func adder(t:int, b:bool): z
	var a :l;
	a[1].i = 1337;
	write a[1].i;
	return 42;
end adder
write(adder(42, true));
#write(3+true);

OUTPUT---------------------------------------------------
type z = int;
type q = record of {i:int};
type l = array of record of {i:int};
func adder(t:int, b:bool): int
   var a:array of record of {i:int};
   a(*array*)(*record*)[1(*int*)](*record*).i(*int*) = 1337(*int*);
   write(a(*array*)(*record*)[1(*int*)](*record*).i(*int*));
   return 42(*int*);
end adder 
write(adder(42(*int*), true(*bool*))(*int*));



incorrectType.raj
INPUT----------------------------------------------------
var a:int;
var b:bool;
a = 42;
b = true;
write((a<5)<(5+b));
OUTPUT---------------------------------------------------
Error:5: incompatible type for expression
Error:5: incompatible type for expression
***2 errors found***
\end{verbatim*}
\section{Appendix}
\subsection{weed.c}
\lstinputlisting{../weed.c}
\subsection{weed.h}
\lstinputlisting{../weed.h}
\subsection{run1.c}
\lstinputlisting{../run1.c}
\subsection{run1.h}
\lstinputlisting{../run1.h}
\subsection{run2.c}
\lstinputlisting{../run2.c}
\subsection{run2.h}
\lstinputlisting{../run2.h}
\subsection{run3.c}
\lstinputlisting{../run3.c}
\subsection{run3.h}
\lstinputlisting{../run3.h}
\subsection{typecheck.c}
\lstinputlisting{../typecheck.c}
\subsection{typecheck.h}
\lstinputlisting{../typecheck.h}
\subsection{symbol.c}
\lstinputlisting{../symbol.c}
\subsection{symbol.h}
\lstinputlisting{../symbol.h}
\subsection{tree.c}
\lstinputlisting{../tree.c}
\subsection{tree.h}
\lstinputlisting{../tree.h}
\subsection{rajahscanner.l}
\lstinputlisting{../rajahscanner.l}
\subsection{rajahparser.y}
\lstinputlisting{../rajahparser.y}
\subsection{memory.h}
\lstinputlisting{../memory.h}
\subsection{memory.c}
\lstinputlisting{../memory.c}
\subsection{tree.h}
\lstinputlisting{../tree.h}
\subsection{tree.c}
\lstinputlisting{../tree.c}
\subsection{pretty.h}
\lstinputlisting{../pretty.h}
\subsection{pretty.c}
\lstinputlisting{../pretty.c}
\subsection{main.c}
\lstinputlisting{../main.c}
\subsection{Makefile}
\lstinputlisting{../Makefile}
\subsection{dangeling\_else\_test.raj}
\lstinputlisting{../test/dangeling_else_test.raj}
\subsection{dangeling\_else\_test.raj}
\lstinputlisting{../test/dangeling_else_test.raj}
\subsection{comments\_test.raj}
\lstinputlisting{../test/comments_test.raj}
\subsection{indentation\_test.raj}
\lstinputlisting{../test/indentation_test.raj}
\subsection{precedence\_test.raj}
\lstinputlisting{../test/precedence_test.raj}
\subsection{nested\_functions\_test.raj}
\lstinputlisting{../test/nested_functions_test.raj}
\subsection{function\_id\_test.raj}
\lstinputlisting{../test/function_id_test.raj}
\subsection{nested\_statements\_test.raj}
\lstinputlisting{../test/nested_statements_test.raj}
\end {document}	

